#include "sort.h"
//////////////打印
void PrintArray(int* a,int n)
{
    for (int i = 0; i < n; ++i)
    {
        printf("%d ",a[i]);
    }
    printf("\n");
}
void Swap(int*x,int*y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}
////////////插入排序
void InsertSort(int* a,int n)
{
    for(int i = 0; i < n-1; i++)
    {
        int end = i;
        int tmp = a[end+1];
        while(end >= 0)
        {
            if(a[end] < tmp)
            {
                break;
            }
            else
            {
                a[end+1] = a[end];
                end--;
            }
        }
        a[end+1] = tmp;
    }
}
////////////冒泡排序
void BubbleSort(int* a, int n)
{
    for(int j = 0; j < n-1; j++)
    {
        int i = 1;
        int count = 0;
        while(i < n-j)
        {
            if(a[i-1] > a[i])
            {
                count = 1;
                Swap(&a[i-1],&a[i]);
            }
            i++;
        }
        if(count == 0)
            break;
    }
}
///////////////堆排序
void AdjustDown(int* a, int n, int root)
{
    //排升序，建大堆
    while (root >= 0)
    {
        int child = root*2 + 1;
        while (child < n)
        {
            if( child+1 < n && a[child] < a[child+1])
            {
                child++;
            }
            if(a[root] < a[child])
            {
                Swap(&a[root],&a[child]);
                root = child;
                child = root*2 + 1;
            }
            else
                break;
        }
        root--;
    }
}
///////////////堆排序
void HeapSort(int* a, int n)
{
    int parent = (n-1-1)/2;
    AdjustDown(a,n,parent);
    while (n - 1 > 0)
    {
        Swap(&a[0],&a[n-1]);
        n--;
        AdjustDown(a,n,0);
    }
}
///////////////希尔排序（交换思想）
void ShellSort(int* a,int n)
{
    int gap = n;
    while(gap > 1)
    {
        gap = gap / 2;
        for(int i = 0; i < n-gap; i++)
        {
            int end = i;
            while(end >= 0)
            {
                if(a[end] > a[end+gap])
                {
                    Swap(&a[end],&a[end+gap]);
                    end = end - gap;
                }
                else
                    break;
            }
        }
    }
}
//////////////希尔排序2
void ShellSort2(int* a, int n)
{
    int gap = n;
    while (gap > 1)
    {
        gap = gap / 2;
//        gap = gap / 3 + 1;

        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end + gap];
            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}
////////////选择排序
void SelectSort(int* a, int n)
{
    int mini = 0;
    int maxi = n-1;
    int begin = 0;
    int end = n-1;
    while(begin < end)
    {
        for (int i = begin; i < maxi+1; ++i)
        {
            if(a[end] < a[i])
            {
                end = i;
            }
            if(a[begin] > a[i])
            {
                begin = i;
            }
        }

        Swap(&a[maxi],&a[end]);
        if(begin == maxi)
            begin = end;
        Swap(&a[mini],&a[begin]);

        mini++;
        maxi--;
        begin = mini;
        end = maxi;
    }
}